Матч 409, Сеть из телепортов (TeleportsNetwork)

Дивизион 2, Уровень 3

Королевство Байтляндия состоит из множества городов, центром которого является столица. Для связи со столицей король решил проложить дороги между городами. Каждый город, кроме столицы, должен построить одну дорогу, ведущую в другой город. Город, в который будет проведена дорога из Х, выбирается по следующему алгоритму:

1. Вычисляем Евклидово расстояние от каждого города Байтляндии до столицы. Выбираем к дальнейшему рассмотрению только те города, расстояния от которых до столицы в точности меньше расстояния от Х до столицы. В выбранное множество городов также включаем столицу;

2. Если выбранное множество содержит более одного города, то то выбираем тот, который ближе всего находится к Х;

3. Если городов, выбранных в пункте 2, несколько, то берем тот, который имеет меньшую x координату;

4. Если городов, выбранных в пункте 3, несколько, то берем тот, который имеет меньшую y координату;

После построения дорого люди стали жаловаться на то, что из некоторых городов стало долго добираться до столицы. Король решил решить эту проблему при помощи постройки teleportCount телепортов. Телепорт можно построить в любом городе, и он мгновенно доставит жителя этого города в столицу.

Неудобством города назовем количество дорог, которое следует пройти его жителю для попадания в столицу. Неудобство столицы и всех городов, в которых содержится телепорт, равно 0. Неудобство города, в котором нет телепорта, но напрямую связанного дорогой со столицей или городом с телепортом, равно 1. Неудобство королевства равно суммарному неудобству городов.

Координаты i - го города заданы в ячейках (citiesX[i], citiesY[i]). Нулевой город является столицей. Распределить teleportCount телепортов между городами так, чтобы неудобство королевства было наименьшим. Вернуть это значение.

Класс: TeleportsNetwork

Метод: int distribute(int teleportCount, vector<int> citiesX,

vector<int> citiesY)

Ограничения: citiesX и citiesY содержат одинаковое количество элементов – от 1 до 50, 0 £ citiesX[i], citiesY[i] £ 1000000, 0 £ teleportCount £ 4.

Вход. Количество телепортов teleportCount и массивы citiesX, citiesY, описывающие координаты городов.

Выход. Величина наименьшего неудобства королевства.

Пример входа

teleportCount	citiesX	citiesY
2	{0,1,1,1,2,2}	{1,0,1,2,0,2}
1	{0,1,1,1,2,2}	{1,0,1,2,0,2}
0	{0,1,1,1,2,3,3,4}	{1,1,2,0,0,0,2,1}

Пример выхода

1

2

5

РЕШЕНИЕ

Флойд-Уоршел + перебор

Построим граф, описанный в условии задачи, в функции BuildGraph. Функция FindCity находит город, к которому будет проведена дорога из city. Массив c в функции FindCity содержит множество городов, расстояние до которых меньше расстояния от city до столицы.

Функция FindDistances вычисляет расстояния между всеми парами городов при помощи алгоритма Флойда-Уоршела. Вес каждой дороги равен 1.

Генерируем все возможные расстановки телепортов в городах (их не более 4) в функции GenCombinations. Для каждой расстановки телепортов вычисляем неудобство королевства при помощи функции KingdomInconv. Среди всех расстановок находим ту, для которой неудобство королевства наименьшее.

ПРОГРАММА

#include <cstdio>

#include <vector>

#include <memory>

#define MAX 2000000000

using namespace std;

int g[51][51],d[51][51];

int n,Result = MAX;

long long dist(long long x1, long long y1, long long x2, long long y2)

{

return (x1 - x2)*(x1 - x2) + (y1 - y2)*(y1 - y2);

}

int FindCity(int city, vector<int> &citiesX, vector<int> &citiesY)

{

vector<int> c;

long long temp,BestDist,MyDist =

dist(citiesX[city],citiesY[city],citiesX[0],citiesY[0]);

int i, iBest;

for(i = 0; i < citiesX.size(); i++)

{

temp = dist(citiesX[i],citiesY[i],citiesX[0],citiesY[0]);

if (temp < MyDist) c.push_back(i);

}

BestDist = (long long)MAX * MAX; iBest=-1;

for(i = 0; i < c.size(); i++)

{

temp = dist(citiesX[city],citiesY[city],citiesX[c[i]],citiesY[c[i]]);

if (temp < BestDist)

{

BestDist = temp; iBest = c[i];

}

else if (temp == BestDist)

if (citiesX[c[i]] < citiesX[iBest] ||

(citiesX[c[i]] == citiesX[iBest] &&

citiesY[c[i]] < citiesY[iBest]))iBest = c[i];

}

return iBest;

}

void BuildGraph(vector<int> &citiesX, vector<int> &citiesY)

{

int i, j, n = citiesX.size();

memset(g,0,sizeof(g));

for(i = 1; i < n; i++)

{

j = FindCity(i,citiesX,citiesY);

g[i][j] = g[j][i] = 1;

}

}

void FindDistances(void)

{

int i, j, k;

memset(d,0x3F,sizeof(d));

for(i = 0; i < n; i++)

{

d[i][i] = 0;

for(j = 0; j < n; j++)

if (g[i][j]) d[i][j] = 1;

}

for(k = 0; k < n; k++)

for(i = 0; i < n; i++)

for(j = 0; j < n; j++)

d[i][j] = min(d[i][j],d[i][k]+d[k][j]);

}

int Inconv(int v,vector<int> &Teleports)

{

int res = d[v][0], i;

for(i = 0; i < Teleports.size(); i++)

res = min(res,d[v][Teleports[i]]);

return res;

}

int KingdomInconv(vector<int> &Teleports)

{

int i,MaxInconv = 0;

for(i = 0; i < n; i++)

MaxInconv = max(MaxInconv,Inconv(i,Teleports));

return MaxInconv;

}

void GenCombinations(int index,int minValue,vector<int> &Teleports)

{

int i;

if (index == Teleports.size())

Result = min(Result,KingdomInconv(Teleports));

else

for(i = minValue; i < n; i++)

{

Teleports[index] = i;

GenCombinations(index+1,i+1,Teleports);

}

}

class TeleportsNetwork

{

public:

int distribute(int teleportCount, vector<int> citiesX, vector<int> citiesY)

{

vector<int> m(teleportCount,0);

n = citiesX.size();

BuildGraph(citiesX,citiesY);

FindDistances();

GenCombinations(0,1,m);

return Result;

}

};